#ifdef LOCAL

#include <bits/stdc++.h>

using namespace std;
#endif

class Solution {
public:
    bool exist(vector<vector<char>> &board, string word) {
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[i].size(); j++) {
                visited[i][j] = true;
                if (board[i][j] == word[0]) dfs(board, word, i, j, 0);
                if (res) return true;
                visited[i][j] = false;
            }
        }
        return false;
    }

    bool visited[7][7];
    bool res;

    void dfs(vector<vector<char>> &board, string word, int i, int j, int num) { //加个引用才能通过所有用例
        if (res) return;
        if (board[i][j] != word[num]) return;
        else if(num == word.size() - 1){
            res = true;
            return;
        }
        else {
            visited[i][j] = true;
            if (i >= 1 && !visited[i - 1][j]) dfs(board, word, i - 1, j, num + 1);
            if (i + 1 < board.size() && !visited[i + 1][j]) dfs(board, word, i + 1, j, num + 1);
            if (j >= 1 && !visited[i][j - 1]) dfs(board, word, i, j - 1, num + 1);
            if (j + 1 < board[i].size() && !visited[i][j + 1])dfs(board, word, i, j + 1, num + 1);
            visited[i][j] = false;
        }
    }
};

#ifdef LOCAL

int main() {
//    freopen('../LeetCode/in.txt', 'r', stdin);
    Solution solution;
    vector<vector<char>> board{{'A', 'B', 'C', 'E'},
                               {'S', 'F', 'C', 'S'},
                               {'A', 'D', 'E', 'E'}};
    string word = "ABCCED";
//    vector<vector<char>> board{{'A', 'A', 'A', 'A', 'A', 'A'},
//                               {'A', 'A', 'A', 'A', 'A', 'A'},
//                               {'A', 'A', 'A', 'A', 'A', 'A'},
//                               {'A', 'A', 'A', 'A', 'A', 'A'},
//                               {'A', 'A', 'A', 'A', 'A', 'A'},
//                               {'A', 'A', 'A', 'A', 'A', 'A'}};
//    string word = "AAAAAAAAAAAAAAB";
    bool res = solution.exist(board, word);
    cout << res;
}

#endif